/// [Truncatable primes](https://projecteuler.net/problem=37)
/// 解题思路：
/// 1. 先获取满足left->right的数字，逆向求解；若n为“Truncatable primes”，则(n/10, >10)为“Truncatable primes”
/// 1. “Truncatable primes”只有首位可能为唯一的偶质数“2”
fn main() {
    let mut buf = vec![vec![2, 3, 5, 7]];
    let mut rst = vec![];
    while rst.len() < 11 {
        let mut row = vec![];
        let exp = buf.len();
        for i in (0..5).map(|x| x * 2 + 1) {
            for j in buf[exp - 1].iter() {
                let n = i * 10_usize.pow(exp as u32) + j;
                if is_prime(n) {
                    row.push(n);
                    if is_r2l(n) {
                        rst.push(n);
                    }
                }
            }
        }
        buf.push(row);
        for i in (1..5).map(|x| x * 2) {
            for j in buf[exp - 1].iter() {
                let n = i * 10_usize.pow(exp as u32) + j;
                if is_prime(n) && is_r2l(n) {
                    rst.push(n);
                }
            }
        }
    }
    for row in buf.iter() {
        println!("{:?}", row);
    }
    println!("{:?}: {}", rst, rst.iter().sum::<usize>());
}

fn is_prime(n: usize) -> bool {
    if n < 2 {
        return false;
    }
    for i in 2..n {
        if n % i == 0 {
            return false;
        }
        if i.pow(2) >= n {
            break;
        }
    }
    true
}

fn is_r2l(n: usize) -> bool {
    if n < 10 {
        return false;
    }
    let mut n = n;
    while n > 0 {
        if !is_prime(n) {
            return false;
        }
        n = n / 10;
    }
    true
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn ok_prime() {
        assert!(!is_prime(1));
        assert!(is_prime(2));
        assert!(is_prime(13));
        assert!(is_prime(137));
        assert!(!is_prime(9));
        assert!(!is_prime(55));
    }
    #[test]
    fn ok_r2l() {
        assert!(!is_r2l(2));
        assert!(is_r2l(3797));
    }
}
